第41章 初等数论

初等数论是研究整数性质的数学分支，其内容在程序设计中有着广泛应用，如密码学、算法优化、数据校验等。

41.1 基本概念与性质

41.1.1 整除

定义：设$a$、$b$为整数，且 $b≠0$，若存在整数$k$使得 $a=b ×k$，则称 $b$ 整除$a$（或$a$能被$b$整除），记作 $b \mid a$。此时$b$是$a$的约（因数），$a$是$b$的倍数。

性质：

1. 若$a \mid b$且$b \mid c$，则$a \mid c$（传递性）。
2. 若$a \mid b$且$a \mid c$，则对任意整数$m$、$n$，有 $a \mid (m ×b+n ×c)$。
3. 若$a \mid b$且$b \mid a$，则$a= \pm b$。
4. 若$b \mid a$，则$b \mid a \times k$（$k$为任意整数）。

41.1.2 素数与合数

• 素数（质数）：大于1的整数，若除了1和自身外没有其他正约数，则称为素数（如2、3、5、7）。
• 合数：大于1的非素数整数（如4、6、8、9）。
• 特殊规定：1既不是素数也不是合数。

性质：

1. 大于2的素数都是奇数。
2. 任何大于1的整数都能分解为素数的乘积（算术基本定理）。

41.1.3 最大公约数与最小公倍数

最大公约数（GCD）：设$a$、$b$为整数，若$d$是同时整除$a$和$b$的最大正整数，则$d$称为$a$ 和$b$的最大公约数，记作$\\gcd(a,b)$。

• 性质：$\\gcd(a,b)=\gcd(b,a \bmod b)$（辗转相除法的理论基础）。
• 互质定义：若 $\gcd(a, b)=1$，则称$a$和$b$互质（互素）。

最小公倍数（LCM）：设$a$、$b$为正整数，若$m$是同时是$a$和$b$的最小正倍数，则$m$称为$a$和$b$的最小公倍数，记作$\text{lcm}(a, b)$。

• 性质：对任意正整数$a$、$b$， $a ×b = \gcd(a, b) × \text{lcm}(a, b)$。

41.2 核心算法与实现

41.2.1 辗转相除法（欧几里得算法）求GCD

// 迭代版：求a和b的最大公约数(a、b为非负整数，且不同时为0)
int gcd(int a,int b){
    while(b!=0){
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 递归版本
int gcdRecursive (int a, int b) {
    if(b == 0) return a;
    return gcdRecursive(b, a % b);
}

41.2.2 最小公倍数(LCM)的计算

// 求a和b的最小公倍数(a、b为正整数)
int lcm(int a,int b){
    return a / gcd(a, b) * b;// 先除后乘，避免溢出
}

41.2.3 素数判定（试除法）

判断一个数$n$是否为素数，只需检查$2 \sim \sqrt{n}$之间的整数能否整除$n$。

// 判断n是否为素数(n≥2)
bool isPrime(int n){
    if (n <= 1) return false;
    if (n == 2) return true;
    if(n % 2 == 0)return false;// 偶数一定不是素数
    for(int i=3;i*i<=n;i+=2){// 只检查奇数
        if(n % i == 0) return false;
    }
    return true;
}

41.2.4 埃氏筛法（筛选素数）

埃氏筛法是筛选$1 \sim n$所有素数的算法，时间复杂度$O(n\log\log n)$。

// 返回标记数组，isPrime[i]为true代表i是素数
vector<bool> sieveOfEratosthenes (int n) {
    vector<bool> isPrime (n + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int p = 2;p * p <= n; p++) {
        if(isPrime[p]){
            for (int i = p * p;i <= n;i += p){
                isPrime[i] = false;
            }
        }
    }
    return isPrime;
}

41.2.5 线性筛法（欧拉筛法）

线性筛时间复杂度$O(n)$，每个合数只会被其最小质因数标记一次，无重复操作。

// 线性筛，返回1~n内所有素数列表
vector<int> linearSieve (int n) {
    vector<bool> isComposite(n + 1,false);
    vector<int> primes;// 存储素数
    for (int i=2;i<=n; ++i) {
        if(!isComposite[i]){
            primes.push_back(i);// i是素数
        }
        // 用已找到的素数筛除合数
        for (int p : primes){
            if(i * p > n) break;
            isComposite[i * p] = true;
            if(i % p == 0)break;// p是i最小质因数，停止循环
        }
    }
    return primes;
}

优势：

1. 不会重复标记合数（如6仅被2标记，不会再被3标记），大数据效率更高；
2. 可同步记录每个数字最小质因数，方便质因数分解。

41.2.6 分解质因数

算术基本定理：任意大于1整数可唯一分解为素数乘积。

#include <map>
// 将n分解，返回{质因数:指数}映射
map<int, int> primeFactorization (int n){
    map<int, int> factors;
    // 处理2的倍数
    while (n % 2 == 0){
        factors[2]++;
        n /= 2;
    }
    // 处理奇数因子
    for (int i=3;i*i<=n;i += 2){
        while (n % i == 0){
            factors[i]++;
            n /= i;
        }
    }
    // 剩余大于2的素数
    if (n > 2){
        factors[n]++;
    }
    return factors;
}

41.3 同余与模运算

41.3.1 同余定义

若整数$a$和$b$除以$m$余数相同，则称$a$与$b$模$m$同余，记作 $a \equiv b \pmod{m}$，等价 $m \mid (a-b)$。

41.3.2 模运算性质

1. $(a+b) \bmod m = [(a \bmod m)+(b \bmod m)] \bmod m$
2. $(a-b) \bmod m = [(a \bmod m)-(b \bmod m)+m] \bmod m$（加$m$避免负数）
3. $(a ×b) \bmod m = [(a \bmod m) ×(b \bmod m)] \bmod m$

快速幂（模幂运算）

高效计算$a^b \bmod m$，时间$O(\log b)$：

long long fastPower(long long a,long long b,long long m){
    long long result=1;
    a %= m;
    while (b > 0){
        if(b % 2 == 1){
            result = (result * a) % m;
        }
        a = (a * a) % m;
        b /= 2;
    }
    return result;
}

41.3.3 同余方程简介

最简同余方程 $a x \equiv b \pmod{m}$，有解充要条件：$\gcd(a, m) \mid b$。 若$\gcd(a, m)=1$，存在模逆元 $a^{\phi(m)-1} \pmod{m}$。

41.4 常用数论定理

41.4.1 算术基本定理

任意大于1整数$n$可唯一分解：

$$n=p_{1}^{k_{1}} × p_{2}^{k_{2}} × \dots × p_{m}^{k_{m}}$$

$p_1<p_2<\dots<p_m$为素数，$k_i$为对应指数。

41.4.2 唯一分解定理推论

设 $a=p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}$，$b=p_1^{b_1}p_2^{b_2}\dots p_k^{b_k}$

$$\\gcd(a,b)=p_1^{\min(a_1,b_1)}p_2^{\min(a_2,b_2)}\dots p_k^{\min(a_k,b_k)}$$ $$\text{lcm}(a,b)=p_1^{\max(a_1,b_1)}p_2^{\max(a_2,b_2)}\dots p_k^{\max(a_k,b_k)}$$

• 因数个数公式：$n$分解后指数$k_1,k_2\dots k_m$，因数总数$(k_1+1)(k_2+1)\dots(k_m)$。 示例：$12=2^2×3^1$，因数个数$(2+1)(1+1)=6$。

41.4.3 欧拉定理

若$\gcd(a, m)=1$，则 $a^{\phi(m)} \equiv 1 \pmod{m}$，$\phi(m)$代表$1\sim m$中和$m$互质数字总数。

41.4.4 费马小定理

若$p$是素数，且$a$不被$p$整除，则 $a^{p-1} \equiv 1 \pmod{p}$。 费马小定理是欧拉定理$m$为素数时的特例（$\phi(p)=p-1$）。

41.5 注意事项

1. 数据溢出：大数运算使用long long替代int。
2. 边界：0不能作为除数；1非素数；2是唯一偶素数。
3. 模负数：C++中负数取模结果为负，需$(x \bmod m + m) \bmod m$转正。
4. 筛法选择：小规模判断素数用试除，大范围批量筛素数用线性筛。

本章41章提取完毕，下一章：第42章 数组模拟高精度计算